package cn.sintang.mianshi;

/**
 * 折半查找实现
 * @author sintang
 * @date 2018-07-15
 */
public class HalfSearch {
    /**
     * 折半查询又叫二分查询
     * 优点：查询次数少，查询速度快，平均性能好。
     * 缺点：需要查询表为有序表，且插入和删除困难
     * 适用于不经常变动而查询频繁的有序列表
     * 步骤：首先假设表中的元素是按照升序排列，将中间位置字段和关键字比对，如果相等则查询成功。
     * 否则利用中间位置将表分成前后两个子表，如果中间字段的值大于关键字，则查询前一个表，否则查询后面一个子表。
     * 重复上个过程。知道满足条件为止。直到子表不存在为止，此时查询不成功。
     */

    public static void main(String[] args) {
        int[] nums = new int[]{2,5,6,10,40,60};
        System.out.println("目标下标："+splitHalfSearch(nums,5));
    }

    /**
     * 折半查询实现1
     * @param nums
     * @param target 关键字
     * @return 返回数组下标
     */
    public static int splitHalfSearch(int[] nums, int target){
        if(nums == null || nums.length == 0){
            return -1;
        }
        // 最低和最高的下标
        int low = 0;
        int high = nums.length;
        int middle = 0;
        int searchCount = 0;
        while(low <= high){
            searchCount++;
            middle = low + (high - low) / 2;
            if(nums[middle] == target){
                System.out.println("搜索次数："+searchCount);
                return middle;
            }else if(nums[middle] > target){
                high = middle -1;
            }else{
                low = middle +1;
            }
        }
        return -1;
    }
}
